class Solution(object):
    def earliestAcq(self, logs, n):
        """
        :type logs: List[List[int]]
        :type n: int
        :rtype: int
        """
        logs.sort()
        self.part = n
        p = [i for i in range(n)]

        def find(x):
            if p[x] == x:
                return x
            else:
                p[x] = find(p[x])
                return p[x]

        def union(x, y):
            rootx = find(x)
            rooty = find(y)
            if rootx != rooty:
                self.part -= 1
                if rootx < rooty:
                    p[rooty] = rootx
                else:
                    p[rootx] = rooty
        for item in logs:
            union(item[1], item[2])
            if self.part == 1:
                return item[0]

        return -1


data = Solution()
logs = [[0, 2, 0], [1, 0, 1], [3, 0, 3], [4, 1, 2], [7, 3, 1]]
n = 4
print(data.earliestAcq(logs, n))
logs = [[20190101,0,1],[20190104,3,4],[20190107,2,3],[20190211,1,5],[20190224,2,4],[20190301,0,3],[20190312,1,2],[20190322,4,5]]
n = 6
print(data.earliestAcq(logs, n))